package com.hot100.mid;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 寻找重复数,可以采用快慢指针
 *
 * @date 2022/10/2 12:55
 */
public class Demo46 {
    public static void main(String[] args) {
        int[] nums=new int[]{3,1,3,4,2};
        System.out.println(findDuplicate1(nums));

    }

    public static int findDuplicate(int[] nums) {
          int  length=nums.length;
          while (length>0){
               //取最后一个位置的数字值
              int num = nums[length - 1];
              if(num==length){
                  length--;
              }else if(num==nums[num-1]){
                  return num;
              }else {
                  int t=nums[num-1];
                  nums[num-1]=nums[length-1];
                  nums[length-1]=t;
              }
          }
          return 0;
    }

    public static int findDuplicate1(int[] nums) {
        int  slow=0,fast=0;
        int  length=nums.length;
        while ((nums[slow%length]!=nums[fast%length])||(slow==fast)){
            //取最后一个位置的数字值
            slow++;
            fast=fast+2;
            slow=slow%length;
            fast=fast%length;

        }
        return nums[slow%length];
    }

}
